# !/usr/bin/env python3
from typing import List

# 左闭右开的情况 [left, right)
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            mid = left + (right - left)//2
            if nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid+1
            else:
                return mid
        # 一定要是左边 因为出循环的时候，left一定比right大，可能比mid大
        return left   


# 左闭右闭的情况 [left, right]
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = left + (right - left)//2
            if nums[mid] > target:
                right = mid-1
            elif nums[mid] < target:
                left = mid+1
            else:
                return mid
        # 一定要是左边 因为出循环的时候，left一定比right大，可能比mid大
        return left   


def main():
    solu = Solution()
    nums = [-1,0,3,5,9,12]
    target = 9
    print(solu.search(nums, target))


if __name__ == '__main__':
    main()